package cn.cxq.learning.single_linked_list;

import java.util.ArrayList;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/f836b2c43afc4b35ad6adc41ec941dba?toCommentId=9129999
 * 来源：牛客网
 *
 * [编程题]复杂链表的复制
 * 热度指数：709851时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
 * 算法知识视频讲解
 * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
 *
 * 说明：本题目包含复杂数据结构ListNode、RandomListNode，点此查看相关信息
 */
public class RandomLinkedList {

    /**
     * 首先我们得十分熟悉使用java的集合工具，对它有深层次的理解，集合里面到底存的是什么，
     * 然后我们才能明白自己克隆到底需要干些什么，为什么需要克隆？克隆是什么？
     * 你到底克隆了指针还是真真正正的在内存里面开辟一块区域让自己克隆的东西真真正正存进去了，这些都很关键，如果不懂这些，自己真的可能只是克隆了一个指针而已。
     * @param pHead
     * @return
     */
    public RandomListNode Clone(RandomListNode pHead) {

        if (pHead == null ) return null;

        RandomListNode cur = pHead;

        ArrayList<RandomListNode> randomListNodes = new ArrayList<>();

        while (cur!=null) {
            randomListNodes.add(cur);
            cur = cur.next;
        }

        ArrayList<RandomListNode> newRandomListNodes = new ArrayList<>();

        cur = randomListNodes.get(0);
        newRandomListNodes.add(new RandomListNode(cur.label));
        cur = cur.next;

        while (cur!=null) {
            newRandomListNodes.add(new RandomListNode(cur.label));
            newRandomListNodes.get(newRandomListNodes.size()-2).next = newRandomListNodes.get(newRandomListNodes.size()-1);
            cur = cur.next;
        }

        for (int i = 0; i < newRandomListNodes.size(); i++) {
            if (randomListNodes.get(i).random!=null) {
                for (int j = 0; j < randomListNodes.size(); j++) {
                    if (randomListNodes.get(i).random == randomListNodes.get(j)) {
                        newRandomListNodes.get(i).random = newRandomListNodes.get(j);
                    }
                }
            }
        }

        return newRandomListNodes.get(0);
    }
}

class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}